// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包fmtsort为地图提供了一个通用的稳定排序机制
// 代表fmt和文本/模板包。
// 不能保证它的效率，它只适用于作为有效映射键的类型
// 。
package fmtsort

import (
	"reflect"
	"sort"
)

// 注意：在整个软件包中，我们避免将reflect.Value.Interface作为
// 这样做并不总是合法的，避免问题比面对问题更容易。

// SortedMap表示映射的键和值。键和值按索引顺序对齐：值[i]是键[i]对应的映射中的值。
type SortedMap struct {
	Key   []reflect.Value
	Value []reflect.Value
}

func (o *SortedMap) Len() int           { return len(o.Key) }
func (o *SortedMap) Less(i, j int) bool { return compare(o.Key[i], o.Key[j]) < 0 }
func (o *SortedMap) Swap(i, j int) {
	o.Key[i], o.Key[j] = o.Key[j], o.Key[i]
	o.Value[i], o.Value[j] = o.Value[j], o.Value[i]
}

// Sort接受一个映射并返回一个SortedMap，该映射具有相同的键和
// 值，但按照键的稳定排序顺序，modulo发出
// 由不可排序的键值（如NaN）引发。
// 
// 排序规则比Go的<运算符：
// 
// /-如果适用，nil比较低
// /-整数、浮点、，按顺序排列的字符串<
// /-NaN比较小于非NaN浮点
// /-bool比较false，而true 
// /-complex比较true，然后imag 
// /-指针按机器地址比较
// /-通道值按机器地址比较
// /-结构依次比较每个字段
// /-数组依次比较每个元素。
// 否则相同的数组将按长度进行比较。
// -接口值首先按描述具体类型的reflect.Type进行比较
// ，然后按前面规则中描述的具体值进行比较。
// 
func Sort(mapValue reflect.Value) *SortedMap {
	if mapValue.Type().Kind() != reflect.Map {
		return nil
	}
	// 注意：此代码被安排为即使在存在并发映射更新的情况下也不会死机。运行时负责
	// 如果发生这种情况，则大声喊叫。见第33275期。
	n := mapValue.Len()
	key := make([]reflect.Value, 0, n)
	value := make([]reflect.Value, 0, n)
	iter := mapValue.MapRange()
	for iter.Next() {
		key = append(key, iter.Key())
		value = append(value, iter.Value())
	}
	sorted := &SortedMap{
		Key:   key,
		Value: value,
	}
	sort.Stable(sorted)
	return sorted
}

// 比较相同类型的两个值。根据a>b（1）、a==b（0）或a<b（-1），它返回-1,0,1 
// 。
// 如果类型不同，则返回-1。
// 有关比较规则，请参见排序注释。
func compare(aVal, bVal reflect.Value) int {
	aType, bType := aVal.Type(), bVal.Type()
	if aType != bType {
		return -1 // 可能没有好的答案，但不要返回0:它们不相等。
	}
	switch aVal.Kind() {
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
		a, b := aVal.Int(), bVal.Int()
		switch {
		case a < b:
			return -1
		case a > b:
			return 1
		default:
			return 0
		}
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
		a, b := aVal.Uint(), bVal.Uint()
		switch {
		case a < b:
			return -1
		case a > b:
			return 1
		default:
			return 0
		}
	case reflect.String:
		a, b := aVal.String(), bVal.String()
		switch {
		case a < b:
			return -1
		case a > b:
			return 1
		default:
			return 0
		}
	case reflect.Float32, reflect.Float64:
		return floatCompare(aVal.Float(), bVal.Float())
	case reflect.Complex64, reflect.Complex128:
		a, b := aVal.Complex(), bVal.Complex()
		if c := floatCompare(real(a), real(b)); c != 0 {
			return c
		}
		return floatCompare(imag(a), imag(b))
	case reflect.Bool:
		a, b := aVal.Bool(), bVal.Bool()
		switch {
		case a == b:
			return 0
		case a:
			return 1
		default:
			return -1
		}
	case reflect.Ptr, reflect.UnsafePointer:
		a, b := aVal.Pointer(), bVal.Pointer()
		switch {
		case a < b:
			return -1
		case a > b:
			return 1
		default:
			return 0
		}
	case reflect.Chan:
		if c, ok := nilCompare(aVal, bVal); ok {
			return c
		}
		ap, bp := aVal.Pointer(), bVal.Pointer()
		switch {
		case ap < bp:
			return -1
		case ap > bp:
			return 1
		default:
			return 0
		}
	case reflect.Struct:
		for i := 0; i < aVal.NumField(); i++ {
			if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
				return c
			}
		}
		return 0
	case reflect.Array:
		for i := 0; i < aVal.Len(); i++ {
			if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
				return c
			}
		}
		return 0
	case reflect.Interface:
		if c, ok := nilCompare(aVal, bVal); ok {
			return c
		}
		c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
		if c != 0 {
			return c
		}
		return compare(aVal.Elem(), bVal.Elem())
	default:
		// 某些类型不能显示为键（映射、函数、切片），而是显式的。
		panic("bad type in compare: " + aType.String())
	}
}

// nilCompare检查其中一个值是否为零。如果不是，则布尔值为false。
// 如果任一值为零，则布尔值为真，整数为比较值
// 值。如果两者都为零，则比较定义为0，否则
// nil值比较低。这两个参数都必须表示chan、func、
// 接口、映射、指针或切片。
func nilCompare(aVal, bVal reflect.Value) (int, bool) {
	if aVal.IsNil() {
		if bVal.IsNil() {
			return 0, true
		}
		return -1, true
	}
	if bVal.IsNil() {
		return 1, true
	}
	return 0, false
}

// floatCompare比较两个浮点值。南斯比较低。
func floatCompare(a, b float64) int {
	switch {
	case isNaN(a):
		return -1 // 如果b是NaN，则没有好的答案，所以不要费心检查。
	case isNaN(b):
		return 1
	case a < b:
		return -1
	case a > b:
		return 1
	}
	return 0
}

func isNaN(a float64) bool {
	return a != a
}
